package zuo.middleLevel_2;


import tools.Tree.Node;
import tools.Tree.Tree;

import java.util.*;

/**
 * @Author: Forx
 * @Data: 2021/6/22
 * @Desc: Algorithm - zuo.middleLevel_2
 * @Version: v1.0
 */
public class ML2 {
    /**
     * 给定一个非负整数n,代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
     * */
    public static int getBTKindes(int n){
        if(n<0)return 0;
        if(n==1||n==0)return 1;
        if(n==2)return 2;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int left=getBTKindes(i);
            int right = getBTKindes(n-i);
            res +=left*right;
        }
        return res;
    }
    public static int getBTKindsOPT(int n){
        return 0;
    }
    /**
     * 1个完整的括号字符串定义规则如下
     * ①空字符串是完整的
     * ②如果s是完整的字符串,那么(s)也是完整的。
     * ③如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
     * 例如,"(00)",""和”(0)"是完整的括号字符串,"O)(","("和"
     * 是不完整的括号字符串。
     * 牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化
     * 为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。
     *
     * */
    public static boolean judgeComp(String string){
        int flag = 0;
        char[] chars = string.toCharArray();
        for (int i = 0; i < string.length(); i++) {
            if(chars[i]=='('){
                flag+=1;
            }else if(chars[i]==')'){
                flag-=1;
                if(flag<0){
                    return false;
                }
            }
        }
        return flag==0;
    }
    public static int getMinComp(String string){
        int flag = 0;
        int ans = 0;
        char[] chars = string.toCharArray();
        for (int i = 0; i < string.length(); i++) {
            if(chars[i]=='('){
                flag+=1;
            }else if(chars[i]==')'){
                flag-=1;
                if(flag<0){
                    ans++;
                    flag=0;
                }
            }
        }
        return flag+ans;
    }
    /**
     * 二叉树每个结点都有一个int型权值,给定一棵二叉树,要求计算出从根结点到
     * 叶结点的所有路径中,权值和最大的值为多少
     *
     * */

    public static int getMaxWeight(Node head){
        if(head!=null){
            if(head.left==null && head.right==null){
                return head.val;
            }
            int leftWeight = getMaxWeight( head.left);
            int rightWeight = getMaxWeight( head.left);
            return Math.max(leftWeight,rightWeight)+head.val;
        }
        return 0;
    }
    /**
     * 给定一个数组arr,求差值为k的去重数字对。
     * [3 2 5 7 0]
     * 有0 2,3 5,5 7
     * */
    public static int[] getDiff(int[] arr,int k){
        Arrays.sort(arr);
        int[] res = new int[arr.length*2];
        int index = 0;
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]==arr[i+1])continue;
            for (int j = 0; i+j < arr.length; j++) {

                if(arr[i+j]-arr[i]>k){
                    break;
                }else if(arr[i+j] - arr[i]==k){
                    res[index] = arr[i];
                    res[index+1] = arr[i+j];
                    index+=2;
                }
            }
        }
        return res;
    }

    /**
     * 给一个包含n个整数元素的集合a,一个包含m个整数元素的集合b。
     * 定义 magic 操作为,从一个集合中取出一个元素,放到另一个集合里,且操作过
     * 后每个集合的平均值都大于操作前。
     * 注意以下两点
     * 1)不可以把一个集合的元素取空,这样就没有平均值了
     * 2)值为x的元素从集合b取出放入集合a,但集合a中已经有值为x的元素,则a的
     * 平均值不变(因为集合元素不会重复),b的平均值可能会改变(因为x被取出
     * 问最多可以进行多少次 magic操作
     * */
    public static int magicOP(int[] arra,int[] arrb){
        double avga = 0;
        double avgb = 0;
        long  sum = 0;

        for (int i = 0; i < arra.length; i++) {
            sum+=arra[i];
        }
        avga = sum/(arra.length-1);
        for (int i = 0; i < arrb.length; i++) {
            sum+=arrb[i];
        }
        avgb = sum/(arrb.length-1);
        int[] bigger = avga>avgb?arra:arrb;
        int[] smaller = bigger==arra?arrb:arra;
        double biggerAvg = Math.max(avga,avgb);
        double smallerAvg =Math.min(avga,avgb);
        Arrays.sort(bigger);
        HashSet<Integer> set = new HashSet<>();
        for(int num:smaller){
            set.add(num);
        }

        int ops = 0;

        int biggerSize = bigger.length-1;
        int smallerSize = smaller.length-1;
        for (int i = 0; i < bigger.length; i++) {
            int cur = bigger[i];
            if(cur > smallerAvg && cur < biggerAvg && !set.contains(cur)){
                smallerAvg = (smallerAvg*smallerSize + cur)/(++smallerSize);
                biggerAvg = (biggerAvg*biggerSize - cur)/(--biggerSize);
                set.add(cur);
                ops++;
            }
        }
        return ops;
    }
    /**
     * 一个合法的括号匹配序列有以下定义：
     * ①空串”是一个合法的括号匹配序列
     * ②如果"X"和"Y"都是合法的括号匹配序列，"XY"也是一个合法的括号匹配序列
     * ③如果“X”是一个合法的括号匹配序列，那么”（X)“也是一个合法的括号匹配序列
     * ④每个合法的括号序列都可以由以上规则生成。
     * 例如：“”，”（)”，”（)()”，”（(())”都是合法的括号序列
     * 对于一个合法的括号序列我们又有以下定义它的深度：
     * ①空串”的深度是0
     * ②如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为
     * max(x,y)3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
     * 例如：“（)()()"的深度是1,"((0))”的深度是3。牛牛现在给你一个合法的括号
     * 序列，需要你计算出其深度。
     *
     * */
    public static int getMaxDeep(String string){
        int flag = 0;
        int max = 0;
        char[] chars = string.toCharArray();
        for (int i = 0; i < string.length(); i++) {
            if(chars[i]=='('){
                flag+=1;
                if(flag>max){
                    max = flag;
                }
            }else if(chars[i]==')'){
                flag-=1;
            }
        }
        return max;
    }
    /**
     * 给定一个()组成的字符串,请找到最长的有效子串
     *
     * */
    public static int getMaxSub(String str){
        if(str==null || str.equals(""))return 0;
        char[] chars = str.toCharArray();
        int[] dp = new int[str.length()];
        int pre = 0;
        int res = 0;
        for (int i = 1; i < chars.length ; i++) {
            if(chars[i]==')'){
                pre = i-dp[i-1]-1;
                if(pre>0 && chars[pre] == '('){
                    dp[i] = dp[i-1] + 2 + (pre>0?dp[pre-1]:0);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
    /**
     *
     * 将给定的数转换为字符串，原则如下：1对应a,2对应b,……26对应z,例如12258
     * 可以转换为"abbeh","aveh","abyh","Ibeh"and"lyh",个数为5,编写一个函
     * 数，给出可以转换的不同字符串的个数。
     *
     * */

    public static int getStrKinds(char[] str,int start){
        if(start == str.length)return 0;
        if(str[start]==0)return 1;
        int ans = 0;
        if(str[start]=='1'){
            ans+=getStrKinds(str,start+1);
            if(start+2<str.length){
                ans+=getStrKinds(str,start+2);
            }
            return ans;
        }else if(str[start]=='2'){
            ans+=getStrKinds(str,start+1);
            if(start+2<str.length && str[start+2] <= '6'){
                ans+=getStrKinds(str,start+2);
            }
            return ans;
        }
        return getStrKinds(str,start+1);
    }
    /**
     * 给定一个元素为非负整数的二维数组matrix,每行和每列都是从小到大有序的。
     * 再给定一个非负整数aim,请判断aim是否在matrix中。
     *
     * 从左上角走,往左走到第一个小于aim的,然后往下走直到第一个大于aim的
     * 然后再往左走,周而复始,如果找到了就返回true,没有就返回false
     *
     * */
    public static boolean isContain(int[][] matrix){

        return false;
    }



    public static void main(String[] args) {
//        System.out.println(judgeComp("((dada))()"));
//        System.out.println(judgeComp("((dad))("));
//        System.out.println(judgeComp("(()dad(dada"));
//        System.out.println(judgeComp("(dada())(("));
//        Node head =  Tree.strToTree("1 2 4 10 # # # # 3 5 # # 6 # # ");
//        Tree.printTree(head);
//
//        System.out.println(getMaxWeight(head));
//        int[] buff = {0,0,0,0,0,0};
//
//        System.out.println( Arrays.toString(getDiff(buff, 2)));

    }

}
